The present invention is directed to the generation of connected graphs on a computer for display on a monitor. Many applications today use graphical displays of their information, notably CAD (computer-aided design) applications, electronic circuit (schematic) design applications, and other graphics programs, particularly "paint" or "draw" programs. Certain applications, such as circuit design applications, include objects displayed on a monitor that are "live" or "intelligent", i.e. correspond to routines of the application that execute functions designed to simulate a real device, such as an electronic circuit.
These applications have in common that they can be used to generate connected graphs on screen, i.e. graphics including objects that are connected by lines, arcs, or the like, often illustrating a functional or hierarchical relationship among the objects. This is true also of applicant's graphical interface application "State Transition Editor", the user's manual. The generation of such connected graphs may be referred to generally as schematic routing.
Graphics produced by such applications are an indispensable tool in the design processes of many areas, such as electronic circuit design and, in the case of applicant's STE, the design of finite state machines to model specifications of applications or of real-life problems and systems. Applications for rendering and displaying computer architectures also rely heavily upon graphics, and it is important that they be clear and readable.
It is important that such graphics be readily intelligible, or they fail at their intended purpose. While CAD and electronic design applications provide for the graphical (and functional) interconnection of displayed objects, they do not provide a mechanism that allows the user to easily read the result; rather, connected graphs produced by applications currently available generally route the connections in a manner convenient to the application, rather than intelligible by the user.
A particular problem in the display of connected graphs is the routing of connections through other connections or through other objects (blocks in a block diagram, for example) appearing on screen. A system is needed for all such applications that can produce schematic routing by intelligently avoiding needless or numerous connection crossovers and collisions with objects.
Graphical objects are typically stored in an object records database. When a region on a screen is accessed by a mouse or other device, conventional systems will conduct a search through the database to determine which object or objects are located at the accessed position. Known approaches to this type of search are those used by Quad-tree, KD-tree, and balanced AVL tree, which are widely used public-domain algorithms.
This type of object location and access is time-consuming, and is particularly inappropriate for a system that must repeatedly and rapidly identify and analyze all objects located at numerous locations. This is a barrier to the design of a system for generating connected graphs, since to analyze many possible connections requires just such repeated identification and analysis of objects and their locations.